/**
 * @author: lk
 * @data: 2021/11/11 14:39
 */
package w7_c1_binary_search;

/**
 * 二分查找
 */
public class BinarySearch {
    private BinarySearch() {
    }


    /**
     * 非递归二分查找
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        int l  = 0, r = data.length-1;
        //不变量：在data[l,r]中寻找target，即[l,r]中所以元素都还没有遍历。因此结束条件是<=。
        while (l <= r) {
            int mid = l + (r-l)/2;
            if(data[mid] .compareTo(target)== 0)
                return mid;
            else if(data[mid].compareTo(target)<0)
                l = mid+1;
            else
                r = mid-1;
        }
        return -1;
    }
    /**
     * 递归二分查找
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r)
            return -1;
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0)
            return mid;
        else if (data[mid].compareTo(target) < 0)
            return searchR(data, mid + 1, r, target);
        return searchR(data, l, mid - 1, target);
    }

}
